/*
Date:20210602 21:45PM
key:经典动态规划，每次最多只用到两个变量，可以只用两个变量来缩小空间.
    坚决不偷懒，马上就用两个变量实现了。
*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        const int n=nums.size();
        //int*dp=new int[n];
        //dp[0]=nums[0];
        int a=nums[0];
        int b=a;
        for(int i=1;i<n;i++)
        {
            //dp[i]=max(dp[i-1]+nums[i],nums[i]);
            a=max(a+nums[i],nums[i]);
            b=max(b,a);
        }
        return b;
    }
};